package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.ArrUtils;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/find-the-distinct-difference-array/">找出不同元素数目差数组</a><br/>
 *      给你一个下标从0开始的数组nums，数组长度为n。<br/>
 *      nums的不同元素数目差数组可以用一个长度为n的数组diff表示，其中diff[i]等于前缀nums[0,...,i]中不同元素的数目减去后缀nums[i+1,...,n-1]中不同元素的数目。<br/>
 *      返回nums的不同元素数目差数组。<br/>
 *      注意nums[i,...,j]表示nums的一个从下标i开始到下标j结束的子数组（包含下标i和j对应元素）。特别需要说明的是，如果i>j，则nums[i,...,j]表示一个空子数组。<br/>
 *      例: <br/>
 *          输入: nums = [1,2,3,4,5]<br/>
 *          输出: [-3,-1,1,3,5]<br/>
 *          解释:
 *              对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 4 个不同的元素。因此，diff[0] = 1 - 4 = -3 。<br/>
 *              对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。<br/>
 *              对于 i = 2，前缀中有 3 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 3 - 2 = 1 。<br/>
 *              对于 i = 3，前缀中有 4 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 4 - 1 = 3 。<br/>
 *              对于 i = 4，前缀中有 5 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 5 - 0 = 5 。<br/>
 * </p>
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/31 13:42
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode2670 {

    /**
     * <p>
     *     找出不同元素数目差数组,通过set集合的唯一性进行判断
     * </p>
     */
    public static int[] distinctDifferenceArray(int[] nums) {
        int N = nums.length;
        Set<Integer> pre = new HashSet<>();
        int[] differ = new int[N];
        for (int i = 0; i < N; i++) {
            pre.add(nums[i]);
            Set<Integer> suf = new HashSet<>();
            for (int j = i + 1; j < N; j++) {
                suf.add(nums[j]);
            }
            differ[i] = pre.size() - suf.size();
        }
        return differ;
    }


    /**
     * <p>
     *     找出不同元素数目差数组
     * </p>
     */
    public static int[] checkDistinctDifferenceArray(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<Integer>();
        int[] sufCnt = new int[n + 1];
        for (int i = n - 1; i > 0; i--) {
            set.add(nums[i]);
            sufCnt[i] = set.size();
        }
        int[] res = new int[n];
        set.clear();
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
            res[i] = set.size() - sufCnt[i + 1];
        }
        return res;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int maxVal = 100;
        int testTimes = 10000;
        System.out.println("Test Start!");
        List<Integer> list = null;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = ArrUtils.generateRandomArr(maxSize, maxVal);
            int[] copiedArr = ArrUtils.copyArr(arr);
            if ( !Arrays.equals(distinctDifferenceArray(arr), checkDistinctDifferenceArray(arr)) ) {
                System.out.println("Oops!");
                ArrUtils.printArr(copiedArr);
                System.out.println();
                break;
            }
        }
        System.out.println("Test End!");
    }
}
